#include <iostream>
#include <vector>
#include <map>

using namespace std;

class Solution
{
    map<int, int> dp;

public:
    int coinChange(vector<int> &coins, int amount)
    {
        if (amount == 0)
        {
            return 0;
        }
        if (dp.find(amount) != dp.end())
            return dp[amount];
        dp[amount] = -1;
        for (auto coin : coins)
        {
            if (amount > coin)
            {
                int count = coinChange(coins, amount - coin);
                if (count != -1)
                {
                    if (dp[amount] == -1)
                        dp[amount] = count + 1;
                    else
                        dp[amount] = min(dp[amount], count + 1);
                }
            }
            else if (amount == coin)
            {
                dp[amount] = 1;
            }
        }
        return dp[amount];
    }
};
int main()
{
    cout << "Code322" << endl;
    Solution s;
    vector<int> coins = {186, 419, 83, 408};
    cout << s.coinChange(coins, 6249) << endl;
    return 0;
}